/*
GINHOUX Alex AND MUTHADA POTTAYYA Ronnie
Veuillez nous excuser pour francais, nous pas parler la france. 
*/


#include <stdio.h>
#include <stdlib.h>

#include "Graphe.h"
#include "automate.h"
#include "liste.h"
#include "listeTrans.h"
#include "iliste.h"
#include "ifile.h"

int main ( void ){
	automate_s *a1 = creer_automate_taille( 5, 2 ), *a2 = creer_automate_taille(3, 2), *tmp;
	ajouteTransition( 0, 1, 'a', a2);
	ajouteTransition(0, 2, 'b', a2);

	ajouteTransition(0, 1, 'a', a1);
	ajouteTransition(0, 2, 'b', a1);
	ajouteTransition(1, 3, 'a', a1);
	ajouteTransition(2, 3, 'a', a1);
	ajouteTransition(3, 4, 'b', a1);

	a2->initial[0] = 1;
	a2->final[1] = 1;
	a2->final[2] = 1;

	a1->initial[0] = 1;
	a1->final[4] = 1;

	printf("\t\t====\tAUTOMATE DE DEPART\t====\n");
	afficheAutomate( a1 );

	printf("\t\t====\tAUTOMATE MINIMISE\t====\n");
	afficheAutomate( minimiseNerode( a1 ) );
	return EXIT_SUCCESS;
}

/*
  La fonction renvoie un automate alloue dynamiquement composé du nombre d'etat passé en parametre, ainsi qu'un nombre d'etiquette egalement passe en parametre.
  Les listes de transitions sont toutes initialise a NULL
  Le tableau initial ainsi que le tableau final est initialise a 0
*/
automate_s* creer_automate_taille( const int nbreEtat, const int nbrEtiquette ){
	int i,j;

	//	on alloue la memoire pour l'automate
	automate_s *autom = (automate_s*) malloc( sizeof( automate_s ) );
	if( autom == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	//	on fixe sa taille et son nombre d'etiquette avec les parametres
	autom->size = nbreEtat;
	autom->sizealpha = nbrEtiquette;
	
	//	on initialise les tableaux d'etats initiaux et finaux à 0
	autom->initial = (int*) malloc(nbreEtat * sizeof( int ) );
	if( autom->initial == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}

	autom->final = (int*) malloc(nbreEtat* sizeof( int ) );
	if( autom->final == NULL ){
	  fprintf( stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	for( i = 0; i < nbreEtat; i++){
		autom->initial[i] = 0;
		autom->final[i] = 0;
	}
	
	//	on cree la structure des tableaux de liste pour les transitions. On initialise toutes les listes a NULL
	autom->trans = (liste_s***) malloc(autom->size * sizeof( liste_s** ) );
	if( autom->trans == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	for (i = 0; i < autom->size; i++){
		autom->trans[i]= (liste_s**) malloc(autom->sizealpha * sizeof( liste_s* ) );
		if( autom->trans[i] == NULL ){
		  fprintf(stderr, "Erreur d'allocation memoire\n");
		  exit( EXIT_FAILURE );
		}
		for (j = 0; j < autom->sizealpha; j++ ){
			autom->trans[i][j]=NULL;
		}
	}
	
	return autom;
}

/*
  Un automate est nerode equivalent si le langage engendre depuis l'etat q1 est equivalent dans le langage engendre depuis l'etat q2
  On creer deux automates avec respectivement l'etat initial q1 puis q2 et on teste leur equivalence 
  La fonction retourne 1 s'ils sont nerode equivalent, autrement 0
  q1 represente le premier etat a tester et q2 represente le deuxieme etat a tester
  automate est l'automate initial contenant q1 et q2 et pour lequel on va tester la nerode equivalence
*/
int nerodeEquivalent( const automate_s const *automate, const int q1, const int q2 ){
	int i,res;
	//	on cree deux automates
	automate_s* automateQ1 = dupliqueAutomate( automate );
	automate_s* automateQ2 = dupliqueAutomate( automate );
	
	//	on fixe le bon etat initial pour chaque automate
	for( i = 0; i < automate->size; i++ ){
		automateQ1->initial[i] = 0;
		automateQ2->initial[i] = 0;
	}
	automateQ1->initial[q1] = 1;
	automateQ2->initial[q2] = 1;

	//	on teste l'inclusion dans les deux sens
	if( isInclu( automateQ1, automateQ2 ) && isInclu( automateQ2, automateQ1 ) )
		res = 1;
	else
		res = 0;

	//	on libere les automates cree en debut de fonction
	libere_automate( &automateQ1 );
	libere_automate( &automateQ2 );

	return res;
}

/*
  Le but de cette fonction est de dupliquer un automate
  automate est l'automate initial dont on veux creer une copie
  On retourne une copie alloue dynamiquement 
*/
automate_s* dupliqueAutomate( const automate_s const *automate ){
	//	on crée un automate vide de meme taille que l'automate a copier
	automate_s* duplication = creer_automate_taille( automate->size, automate->sizealpha);
	int i,j;
	liste_s* liste;
	
	//	on copie les tableaux initiaux et finaux
	for( i = 0; i < automate->size; i++ ){
		duplication->initial[i] = automate->initial[i];
		duplication->final[i] = automate->final[i];
	}
	
	//	on copie toutes les transitions de l'automate a copier
	//	on parcourt tous les etats, pour chaque etat on parcourt toutes les etiquettes
	//	ainsi, on peut parcourir la liste des etats d'arrivee pour ajouter les transitions dans le nouvel automate
	for( i = 0; i < automate->size; i++ ){
		for( j = 0; j < automate->sizealpha; j++ ){
			liste = automate->trans[i][j];
			while( liste != NULL ){
				ajouteTransition( i, liste->state, j+'a', duplication);
				liste = liste->suiv;
			}
		}
	}
	
	return duplication;
}

/*
  automate est l'automate initial qu'on veut completer
  si l'automate n'est pas complet:
    On cree un nouvel etat
    Pour chaque liste de transition vide, on cree une transition vers ce nouvel etat
  On modifie l'automate passe en parametre.
*/
void complete_automate( automate_s *automate ){
	int i,j;
	int *tmp = NULL;

	//	si il est deja complet rien besoin de faire cela permet d'eviter de creer un nouvel etat inutilement
	if( complet( automate ) )
		return;

	//	on incremente la taille de 1
	automate->size++;

	//	on agrandit la taille des tableaux initiaux et finaux en initialisant les cases cree a zero
	automate->initial = realloc( automate->initial, automate->size * sizeof( int ));
	if( automate->initial == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	automate->initial[automate->size-1] = 0;
	automate->final = realloc( automate->final, automate->size * sizeof( int ));
	if( automate->final == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	automate->final[automate->size-1] = 0;
	
	//	on ajoute une case au tableau des etats. On le fait pointer sur un tableau de meme taille que le nombre d'etiquette
	//	puis on initialise la liste des etats d'arrivee a NULL
	automate->trans = (liste_s***) realloc( automate->trans, automate->size * sizeof(liste_s**) );
	if( automate->trans == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	automate->trans[automate->size-1] = (liste_s**) malloc( sizeof( liste_s* ) * automate->size);
	if( automate->trans == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	for( i = 0; i < automate->sizealpha; i++ ){
		automate->trans[automate->size-1][i] = NULL;
	}

	//	on parcourt toutes les listes d'etats d'arrivee
	//	si une liste est vide on ajoute comme etat d'arrivee, l'etat precedement cree (le dernier de l'automate)
	for( i = 0; i < automate->size; i++ ){
		for( j = 0; j < automate->sizealpha; j++ ){
			if( automate->trans[i][j] == NULL ){
				ajouteTransition( i, automate->size-1, j+'a', automate);
			}
		}
	}
}

/*
  Ajout une transition dans un automate.
  on teste si la transition peut exister puis on l'ajoute dans la liste correspondant a l'etat de depart et l'etiquette passes en parametre.
  lettre ( l'etiquette ) doit etre une lettre minuscule reconnu par l'automate
*/
void ajouteTransition( const int depart, const int arrivee, const char lettre, automate_s* automate ){
	//	On test si l'etat de départ existe bien dans l'automate
	if( depart < 0 || depart > automate->size -1 ){
		fprintf(stderr, "Warning! L'etat %d n'existe pas dans le graphe.\n\tLa transition de %d vers %d via '%c' ne sera pas ajouté!\n",depart, depart, arrivee, lettre);
		return;
	}
	//	On test si l'etat d'arrivee existe bien dans l'automate.
	if( arrivee < 0 || arrivee > automate->size -1 ){
		fprintf(stderr, "Warning! L'etat %d n'existe pas dans le graphe.\n\tLa transition de %d vers %d via '%c' ne sera pas ajouté!\n",arrivee, depart, arrivee, lettre);
		return;
	}

	//	On test si la lettre existe bien dans l'automate.
	if( lettre - 97 < 0 || lettre - 97 > automate->sizealpha -1 ){
		fprintf(stderr, "Warning! La lettre %c n'est pas une transition existante.\n\tLa transition de %d vers %d via '%c' ne sera pas ajouté!\n",lettre, depart, arrivee, lettre);
		return;
	}
	
	//	on ajoute l'etat d'arrivee dans la liste correspondant à l'etat de depart et à l'etiquette passe en parametre
	ajouteListe( &(automate->trans[depart][lettre - 97]), arrivee);
}

/*
	Affiche un automate.
	On affiche les etats initiaux puis les etats finaux et enfin les transitions trie par etat de depart puis etiquette
*/
void afficheAutomate(const automate_s const * graphe){
	int i,j;
	liste_s* tmp;

	//	On affiche les etats initiaux
	printf("Les états initiaux :\n");
	for ( i = 0; i < graphe->size; i++ ){
		if( graphe->initial[i] == 1 ){
			printf("%d ",i);
		}
	}
	
	//	On affiche les etats finaux
	printf("\nLes états finaux :\n");
	for ( i = 0; i < graphe->size; i++ ){
		if( graphe->final[i] == 1 ){
			printf( "%d ", i);
		}
	}
	
	//	On affiche les transitions
	//	on parcourt tous les etats, pour chaque etat on parcourt toutes les etiquettes
	//	pour chaque etiquette on parcourt la liste et on affiche l'etat de depart, l'etiquette et l'etat d'arrive
	printf("\n\nLes transitions:\n");
	for (i=0;i<graphe->size;i++){
		printf("-------------------------\n");
		printf("Depuis l'état %d\n",i);
		for(j=0;j<graphe->sizealpha;j++){	
			printf("avec la lettre %c :",97+j);
			tmp  = graphe->trans[i][j];
			while(tmp != NULL){
				printf("%d ",tmp->state);
				tmp=tmp->suiv;
			}
			printf("\n");
		}
	}		
}

/*
 * Compte le nombre de transition dans un graphe.
 * On parcourt chaque etat, pour chacun on parcourt toutes les lettres afin d'atteindre les listes d'etat cible.
 * En parcourant chacune de ces listes on compte le nombre d'etat cible et donc de transition.
 * retourne le nombre de transition(s) dans l'automate
 */
int compte_transition( const automate_s const *graphe){
	//	Compte le nombre de transition de l'automate
	int compteur = 0;
	int i, j;
	//	Permet de parcourir les listes d'etat cible
	liste_s *etat_cible;

	//	on parcourt tous les etats. Pour chaque etat on parcourt les etiquettes
	//	on incremente de un pour chaque element des listes trouvees.
	for( i = 0; i < graphe->size; i++){
		for( j = 0; j < graphe->sizealpha; j++){

			etat_cible = graphe->trans[i][j];

			while( etat_cible ){
				compteur++;
				etat_cible = etat_cible->suiv;
			}
		}
	}

	return compteur;
}

/*
 * Test s'il s'agit d'un automate_s complet.
 * On parcourt chaque etat, chaque etiquette et si la liste_s correspondante est vide alors l'automate_s n'est pas complet.
 */
int complet( const automate_s const *graphe){
	int i, j;

	//	on parcourt tous les etats, pour chaque etat on parcourt les etiquettes.
	//	si on trouve une liste vide on retourne 0
	for( i = 0; i < graphe->size; i++){
		for( j = 0; j < graphe->sizealpha; j++){
			if( graphe->trans[i][j] == NULL )
				return 0;
		}
	}

	//	si on arrive ici c'est qu'aucun liste n'est vide donc l'automate est complet
	return 1;
}

/*
 * Supprime une transition d'un automate.
 * On parcourt la liste_s d'etat cible correspondante à la la transition recherché.
 * On supprime l'element voulu en racordant l'element precedent à l'element suivant (si l'element à supprimer est au milieu ou a la fin de la liste)
 * 		sinon, on fait pointer directement sur le deuxieme element (si l'element à supprimer est le premier de la liste).
 * Finalement on libere la memoire de l'element supprimé.
 */
int supprimeTransition( const int depart, const int arrivee, const char lettre, automate_s* automate){
	liste_s *etat_cible = NULL;
	liste_s *etat_cible_pre = NULL;

	//On test que la transition peut exister.
	//	l'etat de depart est il dans les bonnes bornes
	if( depart < 0 || depart > automate->size -1 ){
		fprintf(stderr, "Erreur! L'etat %d n'existe pas.\n\tLa transition de %d vers %d via '%c' ne peut donc pas etre supprimé!\n", depart, depart, arrivee, lettre);
		return EXIT_FAILURE;
	}
	//	l'etat d'arrivee est il dans les bonnes bornes
	if( arrivee < 0 || arrivee > automate->size-1 ){
		fprintf(stderr, "Erreur! L'etat %d n'existe pas.\n\tLa transition de %d vers %d via '%c' ne peut donc pas etre supprimé!\n", arrivee, depart, arrivee, lettre);
		return EXIT_FAILURE;

	}
	//	l'etiquette existe t'elle
	if( lettre < 97 || lettre - 97 > automate->sizealpha -1 ){
		fprintf(stderr, "Erreur! L'etiquette %c n'existe pas.\n\tLa transition de %d vers %d via '%c' ne peut donc pas etre supprimé!\n",lettre, depart, arrivee, lettre);
		return EXIT_FAILURE;
	}


	etat_cible = automate->trans[depart][lettre - 97];

	//On test si il y a bien des etats cibles pour l'etat de de depart et l'etiquette passe en parametre
	if( etat_cible == NULL ){
		fprintf(stderr, "Warning! La transition de %d vers %d via '%c' n'a pas été trouvé!\n\tAucune suppression n'est effecuté!\n", depart, arrivee, lettre);
		return EXIT_FAILURE;
	}

	//	On test si le premier element de la liste_s est celui recherché.
	if( etat_cible->state == arrivee ){
		automate->trans[depart][lettre - 97] = etat_cible->suiv;
		free( etat_cible );
		return EXIT_SUCCESS;
	}
	//	on memorise l'element precedent pour le racorder à l'element suivant
	etat_cible_pre = automate->trans[depart][lettre - 97];
	etat_cible = etat_cible_pre->suiv;

	//	on parcourt la liste des etats a la recher de l'etat voulu
	while( etat_cible ){
		if( etat_cible->state == arrivee){
			etat_cible_pre->suiv = etat_cible->suiv;
			free( etat_cible );
			return EXIT_SUCCESS;
		}
		etat_cible_pre = etat_cible;
		etat_cible = etat_cible->suiv;
	}

	fprintf(stderr, "Erreur! La transition de %d vers %d via '%c' n'a pas été trouvé!\n\tAucune suppression n'est effecuté!\n", depart, arrivee, lettre);

	return EXIT_FAILURE;

}

/*
 * Supprime l'etat passé par le parametre etat dans l'automate_s pointé par le parametre graphe.
 * On test si l'etat passé en parametre existe. Si c'est le cas, on libere l'espace memoire utilisé par les listes d'etat cible contenu pour chaque etiquette.
 * Ensuite on libere l'espace memoire du tableau contenant les etiquettes.
 * Puis on decale tous les etats dans le tableau des etats, puis on realloue le tableau pour qu'il ait la bonne taille.
 */
void supprimeEtat( const int etat, automate_s* automate){
	int i, j;

	//On test si l'etat existe
	if( etat < 0 || etat > automate->size -1 ){
		fprintf(stderr, "Attention! L'etat %d n'existe pas dans le graphe.\n\tL'etat %d ne peut donc pas etre supprimé.\n", etat, etat);
		return ;
	}

	//On libere les listes d'etats cible
	for( i = 0; i < automate->sizealpha; i++){
		libere_liste( &automate->trans[etat][i] );
	}
	
	//on libere le tableau des transitions
	free( automate->trans[etat] );

	//on reduit le nombre d'etat et on decalle les cases du tableau superieur à l'etat supprime
	automate->size--;
	for( i = etat; i < automate->size; i++ ){
		automate->trans[i] = automate->trans[i+1];
		automate->initial[i] = automate->initial[i+1];
		automate->final[i] = automate->final[i+1];
	}

	//on realloue la memoire pour les transitions, le tableau pour les etats initiaux et le tableau pour le etats finaux
	automate->trans = (liste_s***) realloc( automate->trans, automate->size * sizeof( liste_s** ));
	if( automate->trans == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	automate->initial = (int*) realloc( automate->initial, automate->size * sizeof( int ) );
	if( automate->initial == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	automate->final = (int* ) realloc( automate->final, automate->size * sizeof( int ));
	if( automate->final == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	
	//On supprime toutes les transitions qui vont a notre etat cible passe en parametre
	for( i = 0; i<automate->size; i++){
		for( j = 0; j < automate->sizealpha; j++){
			supprime_element( etat, &automate->trans[i][j] );
		}
	}
	
	//on renomme tous les etats superieurs a l'etat cible
	reduit_transition( automate, etat );

}

/*
  On calcule l'etat le plus grand des deux etats passes en parametre
  On copie le plus grand dans le plus petit
  Ensuite on supprime le plus grand
*/
void fusion_etat( automate_s* automate, const int etat_1, const int etat_2){
	//choisir l'etat le plus petit
	int min,max;
	int i;
	liste_s* tmp;

	if( etat_1 > etat_2 ){
		min = etat_2;
		max = etat_1;
	}else{
		min = etat_1;
		max = etat_2;
	}

	remplace_transition(automate, max, min);
	//on va créer les transitions du plus grand dans le plus petit
	for( i = 0; i < automate->sizealpha; i++){
		tmp = automate->trans[max][i];
		while( tmp != NULL ){
			ajouteTransition( min, tmp->state,'a'+i, automate);
			tmp = tmp->suiv;
		}
	}
	//on supprime le plus grand
	supprimeEtat(max, automate);
}

void reduit_transition( automate_s *automate, const int etat_min ){
	int i,j;
	liste_s *liste;

	for( i = 0; i < automate->size; i++ ){
		for( j = 0; j < automate->sizealpha; j++ ){
			liste = automate->trans[i][j];
			while( liste != NULL ){
				if( liste->state > etat_min )
					liste->state--;
				liste = liste->suiv;
			}
		}
	}
}

void remplace_transition( automate_s* automate, const int search, const int replace ){
	liste_s* tmp;
	int i,j;

	for( i = 0; i < automate->size; i++){
		for( j = 0; j < automate->sizealpha; j++){
			tmp = automate->trans[i][j];
			while( tmp != NULL ){
				if( tmp->state == search )
					tmp->state = replace;
				tmp = tmp->suiv;
			}
		}
	}
}

int langageVide( automate_s *automate ){
	Graphe_s *graphe = automateToGraphe( automate );
	int i,j;

	for( i = 0; i < automate->size; i++){
		if( automate->initial[i] == 1 ){
			for( j = 0; j < automate->size; j++){
				if( automate->final[j] && chemin( graphe, i, j) ){
					libere_graphe( &graphe );
					return 0;
				}
			}
		}
	}

	libere_graphe( &graphe );
	return 1;
}

void supprimeNonCoAccessibles( automate_s* automate ){
	Graphe_s *graphe = automateToGraphe( automate );
	int i,j;
	int a_supprimer;

	for( i = 0; i < automate->size; i++){
		a_supprimer = 1;
		for( j = 0; j < automate->size; j++){
			if( automate->final[j] == 1 && chemin(graphe, i, j) == 1 )
				a_supprimer = 0;
		}
		if( a_supprimer )
			supprimeEtat( i, automate);
	}

	libere_graphe( &graphe );
}

void supprimeNonAccessibles( automate_s *automate ){
	Graphe_s *graphe = automateToGraphe( automate );
	int i,j;
	int a_supprimer;

	for( i = 0; i < automate->size; i++){
		a_supprimer = 1;
		for( j = 0; j < automate->size; j++){
			if( automate->initial[j] == 1 && chemin( graphe, j, i) == 1)
				a_supprimer = 0;
		}
		if( a_supprimer )
			supprimeEtat( i, automate);
	}
	libere_graphe( &graphe );
}

/*
 * Calcul le produit de deux automates passé en parametre.
 */
automate_s* produit( const automate_s const *a1, const automate_s const *a2 ){
	int i,j,k;
	/*
	 * L'automate_s resultant du produit des deux parametres.
	 */
	automate_s *resultat = (automate_s*) malloc( sizeof(automate_s) );
	if( resultat == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	resultat->size = a1->size * a2->size;

	//creation des tableaux initiaux et finaux
	resultat->final = (int*) malloc(sizeof(int) * resultat->size);
	if( resultat->final == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	resultat->initial = (int*) malloc( sizeof(int) * resultat->size);
	if( resultat->initial == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}

	for( i = 0; i < resultat->size; i++ ){
		resultat->initial[i] = 0;
		resultat->final[i] = 0;
	}
	
	for( i = 0; i < a1->size; i++){
		if( a1->initial[i] || a1->final[i] ){
			for( j = 0; j < a2->size; j++ ){
				k = i*a2->size+j;
				if( a1->initial[i] && a2->initial[j] )
					resultat->initial[k] = 1;
				if( a1->final[i] && a2->final[j] )
					resultat->final[k] = 1;
			}
		}
	}

	//calcul du nombre d'etiquette
	if( a1->sizealpha > a2->sizealpha )
		resultat->sizealpha = a1->sizealpha;
	else
		resultat->sizealpha = a2->sizealpha;

	//Initialisation des transitions
	resultat->trans = (liste_s***) malloc( sizeof(liste_s**) * resultat->size );
	if( resultat->trans == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	for( i = 0; i < resultat->size; i++){
		resultat->trans[i] = (liste_s**) malloc( sizeof(liste_s*) * resultat->sizealpha );
		if( resultat->trans[i] == NULL ){
		  fprintf(stderr, "Erreur d'allocation memoire\n");
		  exit( EXIT_FAILURE );
		}
		for( j = 0; j < resultat->sizealpha; j++ ){
			resultat->trans[i][j] = NULL;
		}
	}

	// creation des transitions
	// Pour chaque transition dans l'automate_s 1, on regarde si il y en a une dans l'automate_s 2 avec la meme etiquette
	liste_s *tmp1 = NULL, *tmp2 = NULL;
	for( i = 0; i < a1->size; i++ ){
		for( j = 0; j < a1->sizealpha; j++){
			tmp1 = a1->trans[i][j];
			while( tmp1 != NULL ){
				for( k = 0; k < a2->size; k++){
					if( j < a2->sizealpha ){
						tmp2 = a2->trans[k][j];
						while( tmp2 != NULL ){
							ajouteTransition(i*a2->size+k, tmp1->state*a2->size+tmp2->state, 'a'+j, resultat);
							tmp2 = tmp2->suiv;
						}
					}
				}
				tmp1 = tmp1->suiv;
			}
		}
	}
	
	supprimeNonAccessibles(resultat);
	supprimeNonCoAccessibles(resultat);
	
	return resultat;
}

int intersectionVide( const automate_s const *a1, const automate_s const *a2){
	automate_s *prod = produit( a1, a2 );
	int res;

	res = langageVide( prod );

	libere_automate( &prod );
	return res;
}

void libere_automate( automate_s **a ){
	int i,j;
	automate_s* autom = *a;
	for( i = 0; i < autom->size; i++){
		for( j = 0; j < autom->sizealpha; j++){
			libere_liste( &autom->trans[i][j] );
		}
		free( autom->trans[i] );
	}

	free( autom->trans );

	free( autom->final );
	free( autom->initial );

	free( autom );
	*a = NULL;
}

automate_s* creer_contraire( const automate_s const *base ){
	automate_s *contraire = dupliqueAutomate( base );
	int i,j,k;
	liste_s *arrivee = NULL;

	complete_automate( contraire );

	for( i = 0; i < contraire->size; i++ ){
		if( contraire->final[i] )
			contraire->final[i] = 0;
		else
			contraire->final[i] = 1;
	}

	return contraire;
}

int isInclu( const automate_s const *big, const automate_s const *little ){
	automate_s* complementaire = creer_contraire( big );
	int res;

	if( intersectionVide( complementaire, little ) )
		res = 1;
	else
		res = 0;

	libere_automate( &complementaire );
	return res;
}

automate_s* determinise(automate_s* automaton){
	int etatInitial = rechercheEtatInitial(automaton);
	liste_trans_s *listeTrans = NULL;
	automate_s* newAutomate = NULL;
	iliste_s* tmp = NULL;
	int i, j;

	if (etatInitial == -1){
		fprintf(stderr, "L'automate n'a pas ou a plusieurs états initiaux!!\n");
		return NULL;
	}

	ifile_s* filon = creerIFile();

	initialiseIFileDepart(filon, etatInitial);

	calculeNouveauxEtats(filon, automaton, filon->debut, &listeTrans);

	newAutomate = creer_automate_taille(tailleIListe(filon->debut), automaton->sizealpha);

	newAutomate->initial[0] = 1;

	tmp = filon->debut;
	while(tmp != NULL){
		if (chercheEtatFinalDansFile(automaton, tmp) == 1){
			newAutomate->final[tmp->state] = 1;
		}
		tmp = tmp->suiv;
	}
	liste_trans_s* tmp2 = listeTrans;
	while(listeTrans != NULL){
		ajouteListe(&newAutomate->trans[listeTrans->element->depart][listeTrans->element->etiquette-'a'], listeTrans->element->arrivee);
		listeTrans = listeTrans->suiv;
	}

	libereListeTrans(&tmp2);
	libereFile(&filon);

	return newAutomate;
}

int rechercheEtatInitial(automate_s* automaton){
	int i, etatInitial = -1;
	for (i=0; i<automaton->size; i++){
		if (automaton->initial[i] == 1){
			if (etatInitial == -1){
				etatInitial = i;
			}else{
				return -1;
			}
		}
	}
	return etatInitial;
}

int intInTab( const int valeur, int *tab, const int tailleTab ){
	int i;

	for( i = 0; i < tailleTab; i++ ){
		if ( valeur == tab[i] ){
			return 1;
		}
	}

	return 0;
}

int chercheEtatFinalDansFile(automate_s* automaton, iliste_s* iliston){
	int i;

	for (i=0; i<iliston->tailleVal; i++){
		if (automaton->final[iliston->val[i]] == 1){
			return 1;
		}
	}
	return 0;
}

automate_s* minimise_hopcroft( automate_s* automate ){
	int *prec = (int*) malloc( sizeof(int) * automate->size ), *suiv;
	if( prec == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	int cpt = 0;
	automate_s* nouveau = NULL;
	congruence1( automate, prec);
	suiv = congruenceSuiv( automate, prec);
	while( cpt < 3 && !tableau_equiv(prec, suiv, automate->size) ){
		cpt++;
		free( prec );
		prec = suiv;
		suiv = congruenceSuiv( automate, prec );
		print_tableau_int( suiv, automate->size );
	}
	free( prec );


	nouveau = creer_automate_taille( max_tab( suiv, automate->size ) + 1, automate->sizealpha );

	creer_transition_minimal( nouveau, automate, suiv);
	
	return nouveau;
}

void creer_transition_minimal( automate_s *nouveau, automate_s *precedent, const int *etats ){
	int i,j;
	
	for( i = 0; i < precedent->sizealpha; i++ ){
		for( j = 0; j < precedent->size; j++ ){
			ajouteTransition(etats[j], etats[precedent->trans[j][i]->state], i+'a', nouveau);
		}
	}
}

int max_tab( const int *tab, const int taille ){
	int i,max = 0;
	
	for( i = 1; i < taille; i++ ){
		if( tab[i] > max )
			max = tab[i];
	}
	
	return max;
}

void print_tableau_int( const int * tab, const int taille ){
	int i;
	
	for( i = 0; i < taille; i++ ){
		printf("%d | ", tab[i]);
	}
	printf("\n");	
}

int tableau_equiv( const int* tab1, const int* tab2, const int taille ){
	int i;
	
	for( i = 0; i < taille; i++ ){
		if( tab1[i] != tab2[i] )
			return 0;
	}
	
	return 1;
}

int* congruenceSuiv( automate_s* automate, const int *prec ){
	int *suiv = (int*) malloc( sizeof(int) * automate->size );
	if( suiv == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	int **arrivee = (int**) malloc( sizeof(int*) * automate->sizealpha );
	if( arrivee == NULL ){
	  fprintf(stderr, "Erreur d'allocation memoire\n");
	  exit( EXIT_FAILURE );
	}
	int i, j, max;
	
	for( i = 0; i < automate->sizealpha; i++ ){
	  arrivee[i] = (int*) malloc( sizeof(int) * automate->size );
	  if(arrivee[i]==NULL){
	    fprintf(stderr, "Erreur d'allocation memoire\n");
	    exit( EXIT_FAILURE );
	  }
	}
	
	for( i = 0; i < automate->sizealpha; i++ ){
		for( j = 0; j < automate->size; j++ ){
			arrivee[i][j] = prec[automate->trans[j][i]->state];
		}
	}
	printf(" === TAB INITIAL ===\n");
	print_tableau_int(prec, automate->size);
	printf("\n");
	printf(" === TAB ETIQUETTE ===\n");
	for( i = 0; i < automate->sizealpha; i++ ){
		for( j = 0; j < automate->size; j++ ){
			printf("%d | ", arrivee[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	
	suiv[0] = 0;
	max = 0;
	for( i = 1; i < automate->size; i++ ){
		j = colonne_in_matrice( arrivee, i, automate->sizealpha, i);
		if( j != -1 && prec[i] == prec[j])
			suiv[i] = suiv[j];
		else{
			max++;
			suiv[i] = max;
		}
	}
	
	print_tableau_int( suiv, automate->size);
	
	for( i = 0; i < automate->sizealpha; i++ ){
		free( arrivee[i] );
	}
	free( arrivee );
	return suiv;
}

int colonne_in_matrice( const int **tab, const int colonne, const int maxLigne, const int maxColonne ){
	int i;
	
	for( i = 0; i < maxColonne; i++ ){
		if( i != colonne && colonne_equiv( tab, colonne, i, maxLigne) )
			return i;
	}
	
	return -1;
 }		
		
int colonne_equiv( const int **tab, const int colonne1, const int colonne2, const int maxLigne){
	int i;
	
	for( i = 0; i < maxLigne; i++ ){
		if( tab[i][colonne1] != tab[i][colonne2] )
			return 0;
	}
	
	return 1;
}

void congruence1( automate_s* automate, int *tab ){
	int i;
	
	for( i = 0; i < automate->size; i++ ){
		if( automate->final[i] )
			tab[i] = 1;
		else
			tab[i] = 0;
	}
}

automate_s* minimiseNerode( const automate_s const * base ){
	automate_s* minime = dupliqueAutomate( base );
	int i,j,change;
	do{
		change = 0;
		i = 0;
		while( !change && i < minime->size ){
			j = 0;
			while( !change && j < minime->size ){
				if( i != j && nerodeEquivalent( minime, i, j) ){
					change = 1;
					fusion_etat( minime, i,j );
				}
				j++;
			}
			i++;
		}
	}while( change );
	return minime;
}
